//
// Created by liushuai on 2021/1/21.
//

#include "findMaxForm.h"

int countNum(string &a, char value) {
  int count = 0;
  for (auto elem : a) {
    if (elem == value) count += 1;
  }
  return count;
}

int findMaxForm(vector<string> &strs, int m, int n) {
  int str_nums = strs.size();
  vector<int> rows(n + 1, 0);
  vector<vector<int>> cols(m + 1, rows);
  vector<vector<vector<int>>> DP(str_nums + 1, cols);

  for (int index = 1; index <= str_nums; index++) {
    int ones_nums = countNum(strs[index - 1], '1');
    int zeros_nums = countNum(strs[index - 1], '0');
    for (int i = 0; i <= m; i++) {
      for (int j = 0; j <= n; j++) {
        if (zeros_nums > i || ones_nums > j)
          DP[index][i][j] = DP[index - 1][i][j];
        else {
          DP[index][i][j] =
              max(DP[index - 1][i - zeros_nums][j - ones_nums] + 1,
                  DP[index - 1][i][j]);
        }
      }
    }
  }
  return DP[str_nums][m][n];
}

int findMaxForm1(vector<string> &strs, int m, int n) {
  int str_nums = strs.size();
  int *DP = new int[(m + 1) * (n + 1) * (str_nums + 1)];
  for (int index = 1; index <= str_nums; index++) {
    int ones_nums = countNum(strs[index - 1], '1');
    int zeros_nums = countNum(strs[index - 1], '0');
    for (int i = 0; i <= m; i++) {
      for (int j = 0; j <= n; j++) {
        if (zeros_nums > i || ones_nums > j)
          DP[index * (m + 1) * (n + 1) + (m + 1) * i + j] =
              DP[(index - 1) * (m + 1) * (n + 1) + (m + 1) * i + j];
        else {
          DP[index * (m + 1) * (n + 1) + (m + 1) * i + j] =
              max(DP[(index - 1) * (m + 1) * (n + 1) +
                     (i - zeros_nums) * (m + 1) + j - ones_nums] +
                      1,
                  DP[(index - 1) * (m + 1) * (n + 1) + (m + 1) * i + j]);
        }
      }
    }
  }
  int res = DP[str_nums * (m + 1) * (n + 1) + (m + 1) * m + n];
  delete[] DP;
  return res;
}